package likou

import (
	"container/list"
	"fmt"
)

func A() {
	rst := list.New()
	rst.PushBack(3)
	a := rst.Back()
	fmt.Println(a.Value)
}

// 链表实现的队列: https://studygolang.com/pkgdoc


// 暴力枚举： 1. 首先需要一个函数来验证一个串是否符合条件（isValid）
// 2. 先删除一个字符，看有几种符合， （再在删除一个的基础上）删除两个 。。 len(s) 个。找到所有删除最短的结果，返回即可
// 3. 这样就形成了一个树形结构！ 可以使用层序遍历。 删除最短的结果集合，一定在树的一层上面
// （一）广度优先遍历解题
func RemoveInvalidParentheses(s string) []string {
	// 定义一个队 列
	queue := list.New()
	queue.PushBack(s)
	// 定义结果集
	rst := make([]string, 0)
	// 定义是否找到标志
	var found bool = false
	// 另外进行判断 "()())()("  删除一个字符，可能得到多个结果都是 "()()()(" 的情况， 所以需要去重，重复的就不要进行判断了
	visited := make(map[string]bool)
	visited[s] = true

	for queue.Len() > 0 {
		// 计算一层的元素数量
		size := queue.Len()
		for i := 0; i < size; i++ {
			// 拿到第一个字符串： 先找到第一个元素 queue.Front()， 再删除它， Remove() 自动获取链表节点的 Value
			curStr := queue.Remove(queue.Front()).(string)  // 得到的是 interface 类型，必须要进行转为 string
			// 判断是否是满足条件的
			if isValid(curStr) {
				rst = append(rst, curStr)
				found = true
				// 如果找到了， 也不往下层 继续寻找了
				continue
			}
			// 否则继续向下层寻找
			curStrLen := len(curStr)
			for j := 0; j < curStrLen; j++ {
				if curStr[j] != '(' && curStr[j] != ')' {
					continue
				}
				// 取 去掉当前元素的子字符串
				subStr := curStr[:j] + curStr[j+1:]
				// 添加到队列 之前先进行判断，是否被访问过, 未被访问过，才加入到队列
				if !visited[subStr] {
					queue.PushBack(subStr)
					visited[subStr] = true
				}
			}
		}
		// 如果当前行找到了符合的，那么所有结果都在当前的 行（深度）。 停止向下继续找
		if found { break }
	}
	return rst
}

// 都是 ascll码字符
func isValid(s string) bool {
	count := 0
	for _, c := range s {
		if c == '(' {
			count -= 1
		} else if c == ')' {
			count += 1
		}

		// 大于0，说明有未抵消的 右括号， 那就出错了
		if count > 0 {
			return false
		}
	}
	return count == 0
}
